package leetcode.editor.cn.dsa12_divideAndConquer;
//给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素

public class SortedMatrixSearchLcci1009_1 {
    public static void main(String[] args) {
        Solution solution = new SortedMatrixSearchLcci1009_1().new Solution();
        int[][] matrix = {
                {1,   4,  7, 11, 15},
                {2,   5,  8, 12, 19},
                {3,   6,  9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        System.out.println(solution.searchMatrix(matrix, 5)); //true
        System.out.println(solution.searchMatrix(matrix, 20)); //false
        System.out.println(solution.searchMatrix(matrix, 30)); //true
        System.out.println(solution.searchMatrix(matrix, 100)); //false
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length; if(m == 0) return false; // 行数
            int n = matrix[0].length; if(n == 0) return false; // 列数
            // 定义行指针和列指针，初始位置为右上角元素
            int currentRow = 0, currentColumn = n - 1;
            // 循环结束条件：指针在矩阵外
            while (currentRow < m && currentColumn >= 0) {
                if (matrix[currentRow][currentColumn] == target) {
                    // 当前元素等于目标值，返回true
                    return true;
                } else if (matrix[currentRow][currentColumn] < target) {
                    // 若当前元素小于目标值，指针下移
                    currentRow++;
                } else {
                    // 若当前元素大于目标值，指针左移
                    currentColumn--;
                }
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}